﻿using System;
using System.Collections.Generic;
using STeaL.Functional;

namespace STeaL.Algorithm {
  public static partial class IListExtensions {
#region (internal)
    private static void __push_heap<T>(this IList<T> list, int first, int holeindex, int topindex, T val, Func<T,T,bool> comp) {
      int parent = (holeindex - 1) / 2;
      while (holeindex > topindex && comp(list[first + parent], val) ) {
        list[first + holeindex] = list[first + parent];
        holeindex = parent;
        parent = (holeindex - 1) / 2;
      }
      list[first + holeindex] = val;
    }
    
    private static void __push_heap_aux<T>(this IList<T> list, int first, int last, Func<T,T,bool> comp) {
      list.__push_heap(first, last - first - 1, 0, list[last - 1], comp);
    }
    
    private static void __adjust_heap<T>(this IList<T> list, int first, int holeindex, int len, T val, Func<T,T,bool> comp) {
      int topindex = holeindex;
      int secondChild = 2 * holeindex + 2;
      while (secondChild < len) {
        if (comp(list[first + secondChild], list[first + secondChild - 1])) {
          --secondChild;
        }
        list[first + holeindex] = list[first + secondChild];
        holeindex = secondChild;
        secondChild = 2 * (secondChild + 1);
      }
      if (secondChild == len) {
        list[first + holeindex] = list[first + secondChild - 1];
        holeindex = secondChild - 1;
      }
      list.__push_heap(first, holeindex, topindex,val, comp);
    }
    
    private static void __pop_heap<T>(this IList<T> list, int first, int last, int result, T val, Func<T,T,bool> comp) {
      list[result] = list[first];
      list.__adjust_heap(first, 0, last-first,val,comp);
    } 
    
    private static void __pop_heap_aux<T>(this IList<T> list, int first, int last, Func<T,T,bool> comp) {
      list.__pop_heap(first, last - 1, last - 1, list[last - 1], comp);
    }
    
    private static void __make_heap<T>(this IList<T> list, int first, int last, Func<T,T,bool> comp) {
      if (last - first < 2) return;
      int len = last - first;
      int parent = (len - 2) / 2;
      for ( ; ; ) {
        list.__adjust_heap(first, parent, len, list[first + parent], comp);
        if (parent == 0) return;
        --parent;
      }
    }

#endregion
#region push_heap
    public static void push_heap<T>(this IList<T> list, int first, int last, Func<T,T,bool> comp) {
      list.__push_heap_aux(first, last, comp);
    }
    
    public static void push_heap<T>(this IList<T> list, int first, int last) where T : IComparable<T> {
      list.__push_heap_aux(first, last, rel_op.less<T>);
    }
    
    public static void push_heap<T>(this IList<T> list, Func<T,T,bool> comp) {
      list.__push_heap_aux(0, list.Count, comp);
    }
    
    public static void push_heap<T>(this IList<T> list) where T : IComparable<T> {
      list.__push_heap_aux(0, list.Count, rel_op.less<T>);
    }

#endregion 
#region pop_heap
    public static void pop_heap<T>(this IList<T> list, int first, int last, Func<T,T,bool> comp) {
      list.__pop_heap_aux(first, last, comp);
    }
    
    public static void pop_heap<T>(this IList<T> list, int first, int last) where T : IComparable<T> {
      list.__pop_heap_aux(first, last, rel_op.less<T>);
    }
    
    public static void pop_heap<T>(this IList<T> list, Func<T,T,bool> comp) {
      list.__pop_heap_aux(0, list.Count, comp);
    }
    
    public static void pop_heap<T>(this IList<T> list) where T : IComparable<T> {
      list.__pop_heap_aux(0, list.Count, rel_op.less<T>);
    }

#endregion
#region make_heap
    public static void make_heap<T>(this IList<T> list, int first, int last, Func<T,T,bool> comp) {
      list.__make_heap(first, last, comp);
    }
    
    public static void make_heap<T>(this IList<T> list, int first, int last) where T : IComparable<T> {
      list.__make_heap(first, last, rel_op.less<T>);
    }
    
    public static void make_heap<T>(this IList<T> list, Func<T,T,bool> comp) {
      list.__make_heap(0, list.Count, comp);
    }
    
    public static void make_heap<T>(this IList<T> list) where T : IComparable<T> {
      list.__make_heap(0, list.Count, rel_op.less<T>);
    }
    
#endregion
#region sort_heap
    public static void sort_heap<T>(this IList<T> list, int first, int last, Func<T,T,bool> comp) {
      while (last - first > 1)
        list.pop_heap(first, last--, comp);
    } 
    
    public static void sort_heap<T>(this IList<T> list, int first, int last) where T : IComparable<T> {
      while (last - first > 1)
        list.pop_heap(first, last--, rel_op.less<T>);
    } 
    
    public static void sort_heap<T>(this IList<T> list, Func<T,T,bool> comp) {
      list.sort_heap(0, list.Count, comp);
    }

    public static void sort_heap<T>(this IList<T> list) where T : IComparable<T> {
      list.sort_heap(0, list.Count, rel_op.less<T>);
    }

#endregion
#region sort
    public static void sort<T>(this IList<T> list, int first, int last, Func<T,T,bool> comp) {
      make_heap(list, first, last, comp);
      sort_heap(list, first, last, comp);
    }

    public static void sort<T>(this IList<T> list, int first, int last) where T : IComparable<T> {
      make_heap(list, first, last, rel_op.less<T>);
      sort_heap(list, first, last, rel_op.less<T>);
    }

    public static void sort<T>(this IList<T> list, Func<T,T,bool> comp) {
      make_heap(list,comp);
      sort_heap(list,comp);
    }

    public static void sort<T>(this IList<T> list) where T : IComparable<T> {
      sort(list, rel_op.less<T>);
    }

#endregion
  }
}
